package Offer;

/**
 *  机器人的运动范围
 *  不要回溯,因为每个可以去的格子只能计算一次,走过一次之后再走,也不算数,而回溯回去,只会陷入死循环,回溯回去的位置,其实已经向四方走了
 * @author 是阿秋啊
 * @date 2022/08/10 21:01
 **/
public class Num13 {
    static int count;

    public static int movingCount(int m, int n, int k) {
        if (k == 0) {
            return 1;
        }
        boolean[][] dp = new boolean[m][n];
        helper(dp, 0, 0, k);
        return count;
    }

    public  static void helper(boolean[][] dp, int i, int j, int k) {
        if (!sum(i, j, k)) {
            return;
        }
        if (!dp[i][j]) {
            count++;
            dp[i][j] = true;
        }
        if (i+1<=dp.length - 1 && !dp[i+1][j])
            helper(dp, i + 1, j, k);
        if ( i-1>=0 && !dp[i-1][j] )
            helper(dp, i - 1, j, k);
        if ( j+1<=dp[0].length -1&&!dp[i][j+1])
            helper(dp, i, j + 1, k);
        if ( j - 1 >= 0 && !dp[i][j-1])
            helper(dp, i, j - 1, k);
    }

    public static boolean sum(int m, int n, int k) {
        int sum = 0;
        while (m > 0) {
            sum += m % 10;
            m /= 10;
        }
        while (n > 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum <= k;
    }

    public static void main(String[] args) {
        System.out.println(movingCount(2,3,1));
    }
}